﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;


namespace BloomFilter
{
    public abstract class BloomFilter<TValue> : IDisposable
    {
        /// <summary>
        /// 添加锁
        /// </summary>
        private object addLocker;

        /// <summary>
        /// Hash数据表
        /// </summary>
        private BitArray hashbits;
        /// <summary>
        /// 获取当前Hash表的副本
        /// </summary>
        public BitArray Hashbits
        {
            get 
            {
                return new BitArray(hashbits);
            }
        }

        /// <summary>
        /// 哈希表的字节长度
        /// </summary>
        public int HashByteLength
        {
            get
            {
                //如果长度无法整除，则尾部追加1byte，防止数据溢出
                int i = ((hashbits.Length % 8) != 0) ? 1 : 0;

                //返回校正后的字节长度
                return (hashbits.Length / 8) + i;
            }
        }

        /// <summary>
        /// 每个值的测试数量
        /// </summary>
        private int numKeys;

        #region 构造部分

        /// <summary>
        /// 构造新的过滤器
        /// </summary>
        /// <param name="tableSize">哈希数组大小(字节byte)，大于0的整数</param>
        /// <param name="nKeys">关键值个数</param>
        public BloomFilter(int byteSize, int nKeys)
        {
            Init(nKeys);
            hashbits = new BitArray(byteSize * 8, false);
        }

        /// <summary>
        /// 使用现有数据初始化过滤器
        /// </summary>
        /// <param name="hashTable">现有哈希数组</param>
        /// <param name="nKeys">关键值个数</param>
        public BloomFilter(BitArray hashTable, int nKeys)
        {
            Init(nKeys);
            hashbits = hashTable;
        }

        public BloomFilter(byte[] hashTable, int nKeys)
        {
            Init(nKeys);
            hashbits = new BitArray(hashTable);
        }

        private void Init(int nKeys)
        {
            numKeys = nKeys;
            addLocker = new object();
        }

        #endregion
        /// <summary>
        /// 当前是否包含该值，线程不安全。
        /// </summary>
        /// <param name="val">值</param>
        /// <returns>是否包含</returns>
        public bool IsHave(TValue val)
        {
            if (!IsValid(val))
            {
                return false;
            }

            List<int> hashKeys = CreateHashes(val);
            foreach (int hash in hashKeys)
            {
                if (!hashbits[hash])
                {
                    return false;
                }
            }
            return true;
        }

        /// <summary>
        /// 设置值，线程安全
        /// </summary>
        /// <param name="val">值</param>
        /// <returns>true：当前表中无该值设置成功。false：当前表中已存在该值设置失败</returns>
        public bool Add(TValue val)
        {
            if (!IsValid(val))
            {
                return false;
            }

            bool rslt =false;
            List<int> hashKeys = CreateHashes(val);
            lock (addLocker)
            {
                foreach (int hash in hashKeys)
                {
                    if (!hashbits[hash])
                    {
                        rslt = true;
                        hashbits[hash] = true;
                    }
                }
            }
            return rslt;
        }

        public void Dispose()
        {
            hashbits = null;
        }

        /// <summary>
        /// 将hash数据存储到指定的buffer中
        /// </summary>
        /// <param name="buffer">缓存，尽可能不要null</param>
        public void CopyToBuffer(ref byte[] buffer)
        {
            if (buffer == null || buffer.Length < HashByteLength)
            {
                buffer = new byte[HashByteLength];
            }
            hashbits.CopyTo(buffer, 0);
        }

        #region 重载部分

        /// <summary>
        /// 获取值的hash校验租
        /// </summary>
        /// <param name="val"></param>
        /// <returns></returns>
        protected virtual List<int> CreateHashes(TValue val)
        {
            int hash1 = CreateHash_1(val);
            int hash2 = CreateHash_2(val);

            List<int> result = new List<int>();
            result.Add(Math.Abs(hash1 % hashbits.Count));
            if (numKeys > 1)
            {
                for (int i = 1; i < numKeys; i++)
                {
                    result.Add(Math.Abs((hash1 + (i * hash2)) % hashbits.Count));
                }
            }
            return result;
        }

        /// <summary>
        /// 第一个Hash值获取函数
        /// </summary>
        /// <param name="val"></param>
        /// <returns></returns>
        protected abstract int CreateHash_1(TValue val);

        /// <summary>
        /// 第二个Hash值获取函数
        /// </summary>
        /// <param name="val"></param>
        /// <returns></returns>
        protected abstract int CreateHash_2(TValue val);

        /// <summary>
        /// 判断当前值是否合法有效
        /// </summary>
        /// <param name="val"></param>
        /// <returns></returns>
        protected abstract bool IsValid(TValue val);

        #endregion

    }
}
